package com.example.bm33.bm;

/**
 * @description BM（Boyer-Moore）算法
 * @auther lijiewei
 * @date 2021/12/15 13:58
 */
public class BM {

    private static final int SIZE = 256;

    /**
     * 存放模式串对应的下标，数组下标对应字符的 ASCII 码值
     * @param b 模式串
     * @param m 模式串长度
     * @param bc 存放字符下标的散列表
     * @return
     * @author lijiewei
     * @date   2021/12/15 16:06
     */
    private void generateBC(char[] b, int m, int[] bc) {
        for (int i = 0; i < SIZE; i++) {
            //初始化 bc
            bc[i] = -1;
        }
        for (int i = 0; i < m; i++) {
            int ascii = b[i];
            bc[ascii] = i;
        }
    }

    /**
     * bm 算法，返回模式串在主串完全匹配的起始位置
     * @param a 主串
     * @param n 主串长度
     * @param b 模式串
     * @param m 模式串长度
     * @return
     * @author lijiewei
     * @date   2021/12/15 16:18
     */
    public int bm(char[] a, int n, char[] b, int m) {
        //记录模式串中每个字符最后出现的位置
        int[] bc = new int[SIZE];
        //构建坏字符哈希表
        generateBC(b, m, bc);
        //后缀
        int[] suffix = new int[m];
        boolean[] prefix = new boolean[m];
        //构建好后缀
        generateGS(b, m, suffix, prefix);
        //主串与模式串匹配的第一个字符
        int i = 0;
        while (i <= n-m) {
            int j;
            //模式串从后往前匹配
            for (j = m-1; j>=0; --j) {
                //坏字符对应模式串的下标是j
                if (a[i+j] != b[j]) {
                    break;
                }
            }
            if (j < 0) {
                //匹配成功，返回主串和模式串第一个匹配字符的位置
                return i;
            }
            //坏字符规则需要滑动的位
            int x = j-bc[a[i+j]];
            int y = 0;
            //当 j==m-1, 说明第一个字符就是坏字符，使用不了好后缀规则
            if (j < m-1) {
                y = moveByGS(j, m, suffix, prefix);
            }
            //比较，取最大值滑动
            i = i + Math.max(x, y);
        }
        return -1;
    }

    /**
     * 计算后缀子串
     * @param b 模式串
     * @param m 模式串长度
     * @param suffix 后缀
     * @param prefix 前缀
     * @return
     * @author lijiewei
     * @date   2021/12/15 17:55
     */
    private void generateGS(char[] b, int m, int[] suffix, boolean[] prefix) {
        for (int i = 0; i < m; i++) {
            suffix[i] = -1;
            prefix[i] = false;
        }
        for (int i = 0; i < m-1; i++) {
            int j = i;
            int k = 0;
            while (j>=0 && b[j] == b[m-1-k]) {
                --j;
                ++k;
                suffix[k] = j+1;
            }
            if (j == -1) {
                prefix[k] = true;
            }
        }
    }

    /**
     * 好后缀规则滑动的步长
     * @param j 坏字符对应模式串中的字符下标
     * @param m 模式串长度
     * @param suffix 后缀
     * @param prefix 前缀
     * @return
     * @author lijiewei
     * @date   2021/12/16 11:11
     */
    private int moveByGS(int j, int m, int[] suffix, boolean[] prefix) {
        //长度
        int k = m - 1 - j;
        if (suffix[k] != -1) {
            return j - suffix[k] + 1;
        }
        for (int r = j+2; r <= m-1 ; r++) {
            if (prefix[m-r] == true) {
                return r;
            }
        }
        return m;
    }
}
